package chap3 {
  sealed  trait List[+A]
  case object Nil extends List[Nothing]
  case class Cons[+A](head: A, tail: List[A]) extends List[A]

  object List {
    def sum(insts: List[Int]): Int = insts match {
      case Nil => 0
      case Cons(x, xs) => x + sum(xs)
    }

    def product(ds: List[Double]): Double = ds match {
      case Nil => 1.0
      case Cons(0.0, _) => 0.0
      case Cons(x, xs) => x * product(xs)
    }

    def apply[A](as: A*): List[A] =
      if (as.isEmpty) Nil
      else Cons(as.head, apply(as.tail: _*))

    def tail[A](ds: List[A]): List[A] = ds match {
      case Cons(x, xs) => xs
      case _ => Nil
    }

    def setHead[A](l: List[A], h: A): List[A] = l match {
      case Cons(x, xs) => Cons(h, xs)
      case _ => Cons(h, Nil)
    }

    def drop[A](l: List[A], n: Int): List[A] = {
      var dropCount: Int = 0
      var listTail: List[A] = l
      while (dropCount < n) {
        listTail = List.tail(listTail)
        dropCount = dropCount + 1
      }
      listTail
    }

    def dropWhile[A](l: List[A])(f: A => Boolean): List[A] = l match {
      case Cons(h, t) if (f(h)) => dropWhile(t)(f)
      case _ => l
    }

    def init[A](l: List[A]): List[A] = l match {
      case Cons(h, Nil) => Nil
      case Cons(h, t) => Cons(h, init(t))
      case _ => Nil
    }

    def foldRight[A, B](as: List[A], z: B)(f: (A, B) => B): B = as match {
      case Nil => z
      case Cons(x, xs) => f(x, foldRight(xs, z)(f))
    }

    def length[A](as: List[A]): Int =
      foldRight(as, 0)((a, b) => a match {
        case Nil => b
        case _ => b + 1
      })

    def foldLeft[A, B](as: List[A], z: B)(f: (B, A) => B): B = {
      def foldLeftImpl(as: List[A], ret: B)(d: (B, A) => B): B = as match {
        case Nil => ret
        case Cons(x, xs) => foldLeftImpl(xs, f(ret, x))(f)
      }
      foldLeftImpl(as, z)(f)
    }

    // foldLeft version
    def sum2(as: List[Int]) = foldLeft(as, 0)(_ + _)

    // foldLeft version
    def product2(as: List[Double]) = foldLeft(as, 1.0)(_ * _)

    // foldLeft version
    def length2[A](as: List[A]) =
      foldLeft(as, 0)((b, a) => a match {
        case Nil => b
        case _ => b + 1
      })

    def reverse[A](as: List[A]): List[A] =
      foldLeft(as, Nil: List[A])((b, a) => a match {
        case Nil => b
        case _ => Cons(a, b)
      })

    def foldRight2[A, B](as: List[A], z: B)(f: (A, B) => B): B =
      foldLeft(reverse(as), z)((b, a) => f(a, b))

    def append[A](a1: List[A], a2: List[A]): List[A] =
    a1 match {
      case Nil => a2
      case Cons(h, t) => Cons(h, append(t, a2))
    }

    def append2[A](a: List[A], b: List[A]) : List[A] =
      foldRight(a, foldRight(b, Nil: List[A])(Cons(_, _)))(Cons(_, _))

    def join[A](as: List[A]*): List[A] =
      if (as.isEmpty) Nil
      else append(as.head, join(as.tail: _*))

    def map[A, B](as: List[A])(f: A => B): List[B] = as match {
      case Nil => Nil
      case Cons(h, t) => Cons(f(h), map(t)(f))
    }

    def inc(as: List[Int]): List[Int] = map(as)(_ + 1)

    def tostring(as: List[Double]): List[String] = map(as)(_.toString)

    def filter[A](as: List[A])(f: A => Boolean): List[A] = as match {
      case Cons(h, t) if f(h) => Cons(h, filter(t)(f))
      case Cons(h, t) => filter(t)(f)
      case Nil => Nil
    }

    def filterOdds(as: List[Int]): List[Int] = filter(as)(_ % 2 == 0)

    def join2[A](as: List[List[A]]): List[A] = as match {
      case Cons(h, Nil) => h
      case Cons(h, t) => append(h, join2(t))
      case Nil => Nil
    }

    def flatMap[A, B](as: List[A])(f: A => List[B]): List[B] = join2(map(as)(f))

    // flatMap version
    def filter2[A](as: List[A])(f: A => Boolean): List[A] = flatMap(as)(a => if (f(a)) List(a) else Nil)

    def zipWith[A, B](a: List[A], b: List[A])(f: (A, A) => B): List[B] = a match {
      case Cons(ah, at) => b match {
        case Cons(bh, bt) => Cons(f(ah, bh), zipWith(at, bt)(f))
        case Nil => Nil
      }
      case Nil => Nil
    }

    def zip(a: List[Int], b: List[Int]): List[Int] = zipWith(a, b)(_ + _)
  }

  sealed trait Tree[+A]
  case object TreeNil extends Tree[Nothing]
  case class Leaf[A](value: A) extends Tree[A]
  case class Branch[A](left: Tree[A], right: Tree[A]) extends Tree[A]

  object Tree {
    def size[A](t: Tree[A]): Int = {
      def sizeImpl(t: Tree[A], s: Int): Int = t match {
        case TreeNil => s
        case Leaf(v) => s + 1
        case Branch(l, r) => sizeImpl(l, 0) + sizeImpl(r, 0) + 1
      }
      sizeImpl(t, 0)
    }

    def maximum(t: Tree[Int]): Int = {
      def maxImpl(t: Tree[Int], m: Int): Int = t match {
        case TreeNil => m
        case Leaf(v) => v max m
        case Branch(l, r) => maxImpl(l, 0) max maxImpl(r, 0)
      }
      maxImpl(t, 0)
    }

    def fold[A,B, C](t: Tree[A], z: B)(tr: Tree[A] => B)(f: (B, B) => B): B = {
      def foldImpl[A, B, C](t: Tree[A], d: B, z: B)(tr: Tree[A] => B)(f: (B, B) => B): B = t match {
        case TreeNil => z
        case Leaf(v) => f(tr(t), z)
        case Branch(l, r) => f(f(foldImpl(l, d, d)(tr)(f) , foldImpl(r, d, d)(tr)(f)), tr(t))
      }
      foldImpl(t, z, z)(tr)(f)
    }

    def size2[A](t: Tree[A]): Int = fold(t, 0)(_ => 1)(_ + _)

    def maximum2(t: Tree[Int]): Int = fold(t, 0)((a) => a match {
      case Leaf(v) => v
      case _ => 0})(_ max _)

    def depth[A](t: Tree[A]): Int = fold(t, 0)(_ => 0)(_ max _ + 1)

    def map[A](t: Tree[A])(f: Tree[A] => Tree[A]): Tree[A] = fold(t, TreeNil: Tree[A])(f(_))(Branch(_, _))
  }
}

